home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / pdc / libr / topsort.c < prev   
Encoding:
C/C++ Source or Header  |  1990-04-19  |  9.5 KB  |  415 lines
  1.  
  2. #include "dolib.h"
  3.  
  4. char           *data;
  5. int             left;
  6. int             column;
  7. char            buf[256];
  8. LL            **filetab;
  9. SM             *symhead, *symtail;
  10.  
  11. extern LL      *objhead, *objtail;
  12. extern int      v_flag;
  13. extern char    *malloc();
  14.  
  15. nl(n)
  16. {
  17.     if (column + n > 70) {
  18.         column = 0;
  19.         printf("\n");
  20.     }
  21.     column += n;
  22. }
  23.  
  24. char           *
  25. litlate(s)
  26.     char           *s;
  27. {
  28.     char           *ptr;
  29.  
  30.     ptr = (char *) malloc(strlen(s) + 1);
  31.     strcpy(ptr, s);
  32.     return (ptr);
  33. }
  34.  
  35. SM             *
  36. search_sym(buf)
  37.     char           *buf;
  38. {
  39.     SM             *sp;
  40.  
  41.     for (sp = symhead; sp != NULL; sp = sp->next) {
  42.         if (strcmp(sp->name, buf) == 0)
  43.             return (sp);
  44.     }
  45.     return (NULL);
  46. }
  47.  
  48. SM             *
  49. insert_sym(buf, lp)
  50.     char           *buf;
  51.     LL             *lp;
  52. {
  53.     SM             *sp;
  54.  
  55.     if (symhead == NULL) {
  56.         sp = (SM *) malloc(sizeof(SM));
  57.         sp->name = litlate(buf);
  58.         sp->parent = lp;
  59.         sp->next = NULL;
  60.         symhead = symtail = sp;
  61.     }
  62.     else {
  63.         sp = search_sym(buf);
  64.         if (sp != NULL) {
  65.             if (sp->parent == NULL)
  66.                 sp->parent = lp;
  67.             else {
  68.                 if (lp != NULL && sp->parent != lp) {
  69.                     nl(65);
  70.                     printf("WARNING: Multiple define of %s\n", buf);
  71.                     column = 0;
  72.                 }
  73.             }
  74.         }
  75.         else {
  76.             sp = (SM *) malloc(sizeof(SM));
  77.             sp->name = litlate(buf);
  78.             sp->parent = lp;
  79.             sp->next = NULL;
  80.             symtail->next = sp;
  81.             while (symtail->next != NULL)
  82.                 symtail = symtail->next;
  83.         }
  84.     }
  85.     return (sp);
  86. }
  87.  
  88. long
  89. getl()
  90. {
  91.     long           *ptr;
  92.  
  93.     ptr = (long *) data;
  94.     left -= sizeof(long);
  95.     data += sizeof(long);
  96.     return (*ptr);
  97. }
  98.  
  99. int
  100. load_name()
  101. {
  102.     int             len, code;
  103.     long           *base;
  104.  
  105.     base = (long *) buf;
  106.     len = getl();
  107.     code = (len >> 24) & 0xFF;
  108.     len = (len & 0xFFFFFF);
  109.     while (len-- > 0)
  110.         *base++ = getl();
  111.     *base = 0;
  112.     return (code);
  113. }
  114.  
  115. do_hunk(lp)
  116.     LL             *lp;
  117. {
  118.     long            atomf;
  119.     int             i, j, len, hunk;
  120.     SP             *sp;
  121.  
  122.     hunk = getl();
  123.  
  124.     if (atomf = hunk & 0xC0000000) {
  125.         if (v_flag) {
  126.             nl(10);
  127.             if (atomf == 0x80000000)
  128.                 printf("%10s", "MEMF_FAST");
  129.             else if (atomf == 0x40000000)
  130.                 printf("%10s", "MEMF_CHIP");
  131.         }
  132.         if (atomf == 0xC0000000) {
  133.             atomf = getl();
  134.             if (v_flag) {
  135.                 nl(20);
  136.                 printf("Extra: %08x", atomf);
  137.             }
  138.         }
  139.     }
  140.  
  141.     switch (hunk) {
  142.     case EOF:       /* getl() return eof on endof file */
  143.         break;
  144.     case HunkNone:
  145.         break;
  146.     case HunkEnd:
  147.         if (v_flag) {
  148.             nl(20);
  149.             printf("%10s", "HUNK_END");
  150.         }
  151.         break;
  152.     case HunkDbg:
  153.         if (v_flag) {
  154.             nl(20);
  155.             printf("%10s", "HUNK_DEBUG");
  156.         }
  157.         len = getl();
  158.         for (i = 0; i < len; i++)
  159.             getl();
  160.         break;
  161.     case HunkName:
  162.         load_name();
  163.         if (v_flag) {
  164.             nl(22);
  165.             printf("%10s '%10s'", "HUNK_NAME", buf);
  166.         }
  167.         break;
  168.     case HunkUnit:
  169.     case HunkCode:
  170.     case HunkData:
  171.         if (v_flag) {
  172.             nl(20);
  173.             switch (hunk) {
  174.               case HunkUnit:
  175.                 printf("HUNK_UNIT   ");
  176.                 break;
  177.               case HunkCode:
  178.                 printf("HUNK_CODE   ");
  179.                 break;
  180.               case HunkData:
  181.                 printf("HUNK_DATA   ");
  182.                 break;
  183.             }
  184.         }
  185.         len = getl();
  186.         for (i = 0; i < len; i++)
  187.             j = getl();
  188.         break;
  189.     case HunkBSS:
  190.         if (v_flag) {
  191.             nl(22);
  192.             printf("HUNK_BSS (%08x)", getl());
  193.         }
  194.         else
  195.             getl();
  196.         break;
  197.     case HunkR32:
  198.     case HunkR16:
  199.     case HunkR8:
  200.         if (v_flag) {
  201.             nl(20);
  202.             switch (hunk) {
  203.               case HunkR32:
  204.                 printf("%15s", "HUNK_RELOC32");
  205.                 break;
  206.               case HunkR16:
  207.                 printf("%15s", "HUNK_RELOC16");
  208.                 break;
  209.               case HunkR8:
  210.                 printf("%15s", "HUNK_RELOC8");
  211.                 break;
  212.             }
  213.         }
  214.         for (len = getl(); len > 0; len = getl()) {
  215.             j = getl();
  216.             for (i = 0; i < len; i++)
  217.                 j = getl();
  218.         }
  219.         break;
  220.     case HunkExt:
  221.         if (v_flag) {
  222.             nl(20);
  223.             printf("%10s", "HUNK_EXT");
  224.         }
  225.         for (len = load_name(); len != 0; len = load_name()) {
  226.             sp = (SP *) malloc(sizeof(SP));
  227.             switch (len) {
  228.             case 0x01:
  229.                 if (v_flag) {
  230.                     nl(22);
  231.                     printf(" XDEF %-16s", buf);
  232.                 }
  233.                 sp->entry = insert_sym(buf, lp);
  234.                 sp->next = lp->xdef;
  235.                 lp->xdef = sp;
  236.                 j = getl();
  237.                 break;
  238.             case 0x02:
  239.                 if (v_flag) {
  240.                     nl(22);
  241.                     printf(" XABS %-16s", buf);
  242.                 }
  243.                 sp->entry = insert_sym(buf, lp);
  244.                 sp->next = lp->xdef;
  245.                 lp->xdef = sp;
  246.                 j = getl();
  247.                 break;
  248.             case 0x81:  /* EXT_REF32     */
  249.             case 0x83:  /* EXT_REF16     */
  250.             case 0x84:  /* EXT_REF8      */
  251.                 if (v_flag) {
  252.                     nl(22);
  253.                     printf(" XREF %-16s", buf);
  254.                 }
  255.                 sp->entry = insert_sym(buf, NULL);
  256.                 sp->next = lp->xref;
  257.                 lp->xref = sp;
  258.                 len = getl();
  259.                 for (i = 0; i < len; i++)
  260.                     j = getl();
  261.                 break;
  262.             default:
  263.                 nl(65);
  264.                 printf("WARNING: UNKNOWN reference '%s'\n", buf);
  265.                 column = 0;
  266.                 break;
  267.             }
  268.         }
  269.         break;
  270.     case HunkSym:
  271.         load_name();
  272.         if (v_flag) {
  273.             nl(22);
  274.             printf("%10s '%10s'", "HUNK_SYMBOL", buf);
  275.         }
  276.         len = getl();
  277.         break;
  278.     default:
  279.         nl(65);
  280.         printf("WARNING: UNDEFINED hunk (%08x) in %s\n", hunk,
  281.                 lp->dir_entry.object_filename);
  282.         column = 0;
  283.         break;
  284.     }
  285. }
  286.  
  287. int
  288. compare(x, y)
  289.     LL             *x, *y;
  290. {
  291.     SP             *xp, *yp;
  292.  
  293.     for (yp = y->xref; yp != NULL; yp = yp->next) {
  294.         if (yp->entry->parent == x) {
  295.             for (xp = x->xref; xp != NULL; xp = xp->next) {
  296.                 if (xp->entry->parent == y) {
  297.                     nl(65);
  298.                     printf("WARNING: cycle on files %s, %s\n",
  299.                            x->dir_entry.object_filename,
  300.                            y->dir_entry.object_filename);
  301.                     column = 0;
  302.                     return (FALSE);
  303.                 }
  304.             }
  305.             return (TRUE);
  306.         }
  307.     }
  308.     return (FALSE);
  309. }
  310.  
  311. /*
  312.  * Perform a topological sort of the XDEF and XREF statements
  313.  */
  314.  
  315. topsort()
  316. {
  317.     LL             *lp, *temp;
  318.     SP             *sp, *sp2;
  319.     SM             *sm, *sm2;
  320.     int             i, j, count;
  321.  
  322.     column = 0;
  323.     filetab = NULL;
  324.     symhead = symtail = NULL;
  325.  
  326.     /*
  327.      * Count the number of modules and allocate a temp pointer array
  328.      */
  329.     count = 0;
  330.     for (lp = objhead; lp != NULL; lp = lp->next)
  331.         ++count;
  332.     filetab = (LL **) malloc((count + 1) * sizeof(LL *));
  333.  
  334.     /*
  335.      * Load the modules into the pointer array and store the reference
  336.      * symbols into the symbol table
  337.      */
  338.     count = 0;
  339.     for (lp = objhead; lp != NULL; lp = lp->next) {
  340.         filetab[count++] = lp;
  341.         lp->xdef = lp->xref = NULL;
  342.         data = lp->object_module;
  343.         left = lp->dir_entry.module_size;
  344.         if (v_flag) {
  345.             nl(65);
  346.             printf("%s:\n", lp->dir_entry.object_filename);
  347.             column = 0;
  348.         }
  349.         while (left > 0)
  350.             do_hunk(lp);
  351.     }
  352.  
  353.     /*
  354.      * Sort the modules by exchanging them if they are out of order. Two
  355.      * modules (X,Y) are out of order in a XREF of Y is an XDEF of X.
  356.      */
  357.     for (i = 0; i < count - 1; i++) {
  358.         for (j = i + 1; j < count; j++) {
  359.             if (compare(filetab[i], filetab[j])) {
  360.                 temp = filetab[i];
  361.                 filetab[i] = filetab[j];
  362.                 filetab[j] = temp;
  363.             }
  364.         }
  365.     }
  366.  
  367.     /*
  368.      * Relink the modules in the sorted order
  369.      */
  370.     objhead = objtail = filetab[0];
  371.     objtail->next = NULL;
  372.     for (i = 1; i < count; i++) {
  373.         lp = filetab[i];
  374.         lp->next = NULL;
  375.         objtail->next = lp;
  376.         while (objtail->next != NULL)
  377.             objtail = objtail->next;
  378.     }
  379.  
  380.     /*
  381.      * Free the module symbol reference storage
  382.      */
  383.     for (lp = objhead; lp != NULL; lp = lp->next) {
  384.         sp = lp->xdef;
  385.         while (sp != NULL) {
  386.             sp2 = sp;
  387.             sp = sp->next;
  388.             free(sp2);
  389.         }
  390.         sp = lp->xref;
  391.         while (sp != NULL) {
  392.             sp2 = sp;
  393.             sp = sp->next;
  394.             free(sp2);
  395.         }
  396.     }
  397.  
  398.     /*
  399.      * Free the symbol table
  400.      */
  401.     sm = symhead;
  402.     while (sm != NULL) {
  403.         sm2 = sm;
  404.         sm = sm->next;
  405.         free(sm2->name);
  406.         free(sm2);
  407.     }
  408.     free(filetab);
  409.  
  410.     nl(65);         /* Reset the column counter  */
  411.     column = 0;
  412.  
  413.     return (0);
  414. }
  415.